package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}17:28
 */
public class interview47 {

    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(maxValue(grid));
    }

    public static int maxValue(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        //进行前缀和
        for (int i = 1; i < col; i++){
            grid[0][i] += grid[0][i-1];
        }
        for (int j = 1; j < row; j++){
            grid[j][0] += grid[j-1][0];
        }
        //进行内部一张二维表的动态规划
        for (int i = 1; i < row;i++){
            for (int j = 1; j < col;j++){
                grid[i][j] += Math.max(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[row-1][col-1];
//        while (true){
//            if (i==grid.length-1&&j==grid[i].length-1){
//                break;
//            }
//            if (j == grid[i].length-1){
//                res += grid[i+1][j];
//                i++;
//            }else if (i == grid.length -1){
//                res += grid[i][j+1];
//                j++;
//            } else if (grid[i+1][j] > grid[i][j+1]){
//                res += grid[i+1][j];
//                i++;
//            } else {
//                res += grid[i][j+1];
//                j++;
//            }
//        }
    }
}
